package sun.scheduler.util.graph;

import java.lang.reflect.Array;
import java.util.*;
import sun.scheduler.util.graph.algorithm.maxflow.Label;
import sun.scheduler.util.graph.algorithm.maxflow.ResidualEdgeData;

/**
 * A simple graph data structure that can be used if the maximum amount of nodes
 * is known. The structure is managed by id's. Hence adding and removing nodes
 * should be used in a restricted way. The structure is optimized for fast
 * accsess of nodes and edges in (O(0) time).
 *
 * @param <N> the data associated to each node
 * @param <E> the data associated to each edge
 * @author Martin Jutzi
 */
public class Graph<N, E> implements Iterable<Node<N, E>>
{

    private int edgeModCount = 0;
    // counter for next id
    private int nextId = 0;
    // number of nodes
    private int numOfNodes = 0;
    // number of edges
    private int numOfEdges = 0;
    // maximum number of nodes allowed
    private int capacity;
    private ArrayList<Node<N, E>> topologicalOrder;
    //remember the last mod count 
    private int topOrderModCount = 0;
    /**
     * array which stores all nodes
     */
    protected Node<N, E>[] nodes;

    /**
     * Creates a new graph with the maximum node capacity
     *
     * @param capacity the node capacity
     */
    public Graph(int capacity)
    {
        if (capacity < 0)
            throw new IllegalArgumentException("Negative capacity.");

        this.capacity = capacity;
        nodes = (Node<N, E>[]) Array.newInstance(Node.class, capacity);
        topologicalOrder = new ArrayList<Node<N, E>>(capacity);
    }

    /**
     * Gets the amount of addable nodes.
     *
     * @return amount of addable nodes
     */
    public int getFreeCapacity()
    {
        return Math.max(capacity - nextId, 0);
    }

    /**
     * Gets th capacity of this Graph.
     *
     * @return th capacity.
     */
    public int getCapacity()
    {
        return capacity;
    }

    /**
     * Gets the number of edge modifications.
     *
     * @return edgeModCount
     */
    public int getEdgeModCount()
    {
        return edgeModCount;
    }

    /**
     * Gets an array containing all nodes.
     *
     * @return
     */
    public Node<N, E>[] getNodes()
    {
        return Arrays.copyOf(nodes, nextId);
    }

    /**
     * Gets the number of edges that where added to this graph.
     *
     * @return number of edges
     */
    public int getNumOfEdges()
    {
        return numOfEdges;
    }

    /**
     * Gets the number of nodes that where added to this graph.
     *
     * @return number of nodes
     */
    public int getNumOfNodes()
    {
        return numOfNodes;
    }

    /**
     * Gets the node assoziated with its id.
     *
     * @param id node id
     * @return node assoziated with its id
     */
    public Node<N, E> getNode(int id)
    {
        checkId(id);
        return nodes[id];
    }

    /**
     * Checks the if he specified id is set, i.e. if a node with the id was
     * added.
     *
     * @param id the specified node id
     * @throws IndexOutOfBoundsException if {
     * @see id < 0 } or {@see nextId < id }
     */
    protected void checkId(int id)
            throws IndexOutOfBoundsException
    {
        if (id < 0 || nextId <= id)
            throw new IndexOutOfBoundsException("Invalid node id " + id + " .");
    }

    /**
     * Adds a new node to this graph structure.
     *
     * @param data the data assoziated with this node.
     * @return the created node.
     */
    public <D extends N> Node<N, E> addNode(D data)
    {
        if (nextId == capacity)
            throw new IllegalStateException("Overflow of max number of nodes.");

        Node<N, E> node = new Node<N, E>(nextId, data, this);
        nodes[nextId] = node;
        nextId++;
        numOfNodes++;
        return node;
    }

    /**
     * Adds a new Edge to this connecting two nodes specified by their id.
     *
     * @param sId id of the start node
     * @param eId id of the end node
     * @param data data content of this edge
     * @return the edge added to this graph.
     * @throws IllegalArgumentException if either the start or the endnode is
     * unknown, or the edge is already defined
     * @throws IndexOutOfBoundsException if the indeces are invalid.
     */
    public <D extends E> Edge<N, E> addEdge(int sId, int eId, D data)
    {
        checkId(sId);
        checkId(eId);

        Node<N, E> start = nodes[sId];
        Node<N, E> end = nodes[eId];
        Edge<N, E> edge = new Edge<N, E>(data, start, end, this);

        start.addOutgoingEdge(edge);
        end.addIncomingEdge(edge);

        numOfEdges++;
        edgeModCount++;
        return edge;
    }

    /**
     * Removes an edge connecting two nodes of this graph.
     *
     * @param edge the edge that should be removed
     * @return the removed edge
     * @throws IllegalArgumentException if the edge is node an element of this
     * graph
     */
    public Edge<N, E> removeEdge(Edge<N, E> edge)
    {
        try
        {
            if (edge.graph != this)
                throw new IllegalArgumentException("Wrong graph.");

            edge.start.removeOutgoingEdge(edge);
            edge.end.removeIncomingEdge(edge);

            numOfEdges--;
            edgeModCount++;
            return edge;
        }
        catch (NullPointerException ex)
        {
            throw new IllegalArgumentException("null");
        }
    }

    /**
     * Gets an BFSIterator node iterator that traverses through all nodes.
     *
     * @return a new Instance of the {@link BFSIterator }
     */
    public BFSIterator<N, E> getBFSIterator()
    {
        return new BFSIterator<N, E>(this);
    }

    /**
     * Gets an BFSIterator node iterator that traverses through all nodes, that
     * are reachable by some outgoing path starting from a specified node
     *
     * @param node the node from which to start the traversion.
     * @return a new Instance of the {@link BFSIterator }
     */
    public BFSIterator<N, E> getBFSIterator(int id)
    {
        return new BFSIterator<N, E>(getNode(id));
    }

    /**
     * Gets an BFSIterator node iterator that traverses through all nodes, that
     * are reachable by some outgoing path starting from a specified node
     *
     * @param node the node from which to start the traversion.
     * @return a new Instance of the {@link BFSIterator }
     */
    public BFSIterator<N, E> getBFSIterator(Node<N, E> node)
    {
        return new BFSIterator<N, E>(node);
    }

    /**
     * Gets an EdgeIterator that traverses through all edges of this graph.
     *
     * @return a new Insatnce of the {@link EdgeIterator }
     */
    public EdgeIterator<N, E> getEdgeIterator()
    {
        return new EdgeIterator<N, E>(this);
    }

    @Override
    public String toString()
    {
        StringBuilder strB = new StringBuilder();

        strB.append(" Nodes: ");
        for (int i = 0; i < numOfNodes; i++)
            strB.append(nodes[i]);

        strB.append("\n Edges: ");
        EdgeIterator<N, E> edgeIterator = getEdgeIterator();
        while (edgeIterator.hasNext())
            strB.append(edgeIterator.next()).append(" ");

        return strB.toString();
    }

    /**
     * Applies a topologic order onto the graph if it is cycle free.
     *
     * @return topologically orderd Nodes
     */
    public ArrayList<Node<N, E>> topologicOrder() throws IllegalStateException
    {
        if (topOrderModCount != edgeModCount)
        {
            updateTopologicalOrder();
            topOrderModCount = edgeModCount;
        }
        return topologicalOrder;
    }

    /*
     * Recomputes the topological order of this graph asuming that its cycle
     * free.
     */
    private void updateTopologicalOrder()
    {
        int[] predCounts = new int[numOfNodes];
        topologicalOrder = new ArrayList<Node<N, E>>(numOfNodes);
        Queue<Node<N, E>> predLess = new LinkedList<Node<N, E>>();

        for (int i = 0; i < numOfNodes; i++)
        {
            Node<N, E> node = nodes[i];
            if ((predCounts[i] = node.inEdges.size()) == 0 && !node.outEdges.isEmpty())
                predLess.offer(node);
        }

        while (!predLess.isEmpty())
        {
            Node<N, E> curr = predLess.poll();

            for (Node<N, E> next : curr)
                if (--predCounts[next.id()] == 0)
                    predLess.add(next);

            curr.setOrderID(topologicalOrder.size());
            topologicalOrder.add(curr);
        }

    }

    @Override
    public Iterator<Node<N, E>> iterator()
    {
        return new Iterator<Node<N, E>>()
        {

            int currPosition = 0;

            @Override
            public boolean hasNext()
            {
                return currPosition < nextId;
            }

            @Override
            public Node<N, E> next()
            {
                return getNode(currPosition++);
            }

            @Override
            public void remove()
            {
                throw new UnsupportedOperationException("Not supported yet.");
            }

        };
    }

    /**
     * Gets the outgoing edge connecting two nodes.
     *
     * @param startId the start id
     * @param endId the end id
     * @return the {@link Edge} between these two nodes or null if such an edge
     * does not exist
     * @throws IndexOutOfBoundsException if the indeces are invalid.
     */
    public Edge<N, E> getEdge(int startId, int endId)
    {
        checkId(startId);
        checkId(endId);

        Node<N, E> start = getNode(startId);
        for (Edge<N, E> edge : start.getOutEdges())
            if (edge.getEnd().id == endId)
                return edge;

        return null;
    }

    /**
     * Removes the outgoing edge connecting two nodes.
     *
     * @param startId the start id
     * @param endId the end id
     * @return the removed edge, or {@code null} if no edge was removed
     * @throws IndexOutOfBoundsException if the indeces are invalid.
     */
    public Edge<N, E> removeEdge(int startId, int endId)
    {
        checkId(startId);
        checkId(endId);

        Node<N, E> start = getNode(startId);
        ListIterator<Edge<N, E>> listIterator = start.getOutEdges().listIterator();
        while (listIterator.hasNext())
        {
            Edge<N, E> edge = listIterator.next();
            if (edge.getEnd().id == endId)
            {
                listIterator.remove();
                getNode(endId).inEdges.remove(edge);
                edgeModCount++;
                numOfEdges--;
                return edge;
            }
        }

        return null;
    }
}
